SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Robertson–Webb query model</title>

</head>

Robertson–Webb query model

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, the Robertson–Webb (RW) query model is a <a href="Model_of_computation" title="Model of computation">model of computation</a> used by algorithms for the problem of <a href="Fair_cake-cutting" title="Fair cake-cutting">fair cake-cutting</a>. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query (also called a Mark query) asks an agent to specify a piece of cake with a given value.

Despite the simplicity of the model, many classic cake-cutting algorithms can be described only by these two queries. On the other hand, there are fair cake-cutting problems that provably cannot be solved in the RW model using finitely many queries.

The Eval and Cut queries were first described in the book of Jack M. Robertson and William A. Webb.<a href="#cite_note-book-1">[1]</a> The name "Robertson–Webb model" was coined and formalized by Woeginger and Sgall.<a href="#cite_note-ws07-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

The standard RW model assumes that the cake is an interval, usually the interval [0,1]. There are n agents, and each agent i has a value measure vi on the cake. The algorithm does not know vi, but can access it using two kinds of queries:

<ul><li>An eval query: given two real numbers x and y, Evali(x,y) asks agent i to report the value of the interval [x,y], i.e., vi ([x,y]).</li>

<li>A mark query (also called a cut query): given two real numbers x and r, Marki(x,r) asks agent i to report some value y such that vi([x,y]) = r.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

The classic <a href="Divide_and_choose" title="Divide and choose">Divide and choose</a> algorithm, for cutting a cake between two children, can be done using four queries.

<ul><li>Ask Alice an Eval(0,1) query; let V1 be the answer (this is Alice's value of the entire cake).</li>

<li>Ask Alice a Mark(0, V1 / 2) query; let x1 be the answer (this is Alice's mark which yields two pieces equal in her eyes).</li>

<li>Ask George an Eval(0, x1) and an Eval(x1, 1) queries.</li>

<li>If the former value is larger, give (0,x1) to George and (x1,1) to Alice; else, give (0,x1) to Alice and (x1,1) to George.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Results">Results</h2></div>

Besides divide-and-choose, many cake-cutting algorithms can be performed using RW queries whose number is polynomial in n (the number of agents). For example: <a href="Last_diminisher" title="Last diminisher">Last diminisher</a> can be done by O(n2) RW queries and <a href="Even%E2%80%93Paz_protocol" title="Even–Paz protocol">Even–Paz protocol</a> can be done by O(n log n) RW queries. In parallel, there are many hardness results, proving that certain fair division problems require many RW queries to complete. Some such hardness results are shown below.

<a href="Proportional_cake-cutting" title="Proportional cake-cutting">Proportional cake-cutting</a> requires Ω(n log n) RW queries when either

<ul><li>the pieces must be connected,<a href="#cite_note-ws07-2">[2]</a> or</li>

<li>the protocol is deterministic,<a href="#cite_note-ep06neg-3">[3]</a> or</li>

<li>the precision of cutting the cake is finite.<a href="#cite_note-ep06neg-3">[3]</a></li>

<li>The only protocol which uses O(n) RW queries is a randomized protocol, which can return disconnected pieces, and the allocation might be only fractionally-proportional.</li></ul>

<a href="Proportional_cake-cutting_with_different_entitlements" title="Proportional cake-cutting with different entitlements">Proportional cake-cutting with different entitlements</a> requires at least Ω(n log(D)) RW queries, where D is the common denominator of the entitlements (in particular, it cannot be found using a bounded number of queries if the entitlements are irrational). There is an algorithm that uses O(n log(D)) RW queries for rational entitlements, and a finite algorithm for irrational entitlements.<a href="#cite_note-4">[4]</a>

<a href="Envy-free_cake-cutting" title="Envy-free cake-cutting">Envy-free cake-cutting</a> requires

<ul><li>Ω(n2) RW queries when the pieces may be disconnected,<a href="#cite_note-5">[5]</a></li>

<li>Infintiely many queries when the pieces must be connected and there are at least 3 agents.<a href="#cite_note-6">[6]</a> In other words, there is no algorithm that always finds an envy-free allocation among 3 or more agents using finitely-many RW queries.</li>

<li>For any ε > 0, an ε-envy-free connected cake-cutting requires at least Ω(log ε−1) queries.<a href="#cite_note-:0-7">[7]</a> For 3 agents, an O(log ε−1) protocol exists. For 4 agents, an O(poly(log ε−1)) protocol exists.<a href="#cite_note-8">[8]</a> For 5 or more agents, the best known protocol requires O(n ε−1), which shows an exponential gap in the query complexity.</li></ul>

<a href="Equitable_cake-cutting" title="Equitable cake-cutting">Equitable cake-cutting</a> cannot be done using finitely-many RW queries even for 2 agents.<a href="#cite_note-:2-9">[9]</a> Moreover, for any ε > 0:

<ul><li>A connected ε-equitable cake-cutting requires at least Ω(log ε−1) queries.<a href="#cite_note-:0-7">[7]</a> For 2 agents, an O(log ε−1) protocol exists.<a href="#cite_note-cp11-10">[10]</a> For 3 or more agents, the best known protocol requires O(n (log n + log ε−1)) queries.<a href="#cite_note-:1-11">[11]</a></li>

<li>Even without connectivity, ε-equitable cake-cutting requires at least Ω(log ε−1 / log log ε−1 ) RW queries.<a href="#cite_note-:2-9">[9]</a></li></ul>

<a href="Exact_cake-cutting" class="mw-redirect" title="Exact cake-cutting">Exact cake-cutting</a> (also known as perfect cake-cutting) cannot be done using finitely-many RW queries even for 2 agents. Moreover, for any ε > 0:

<ul><li>An ε-perfect cake-cutting with the minimum possible number of cuts requires at least Ω(log ε−1) queries. For 2 agents, an O(log ε−1) protocol exists.<a href="#cite_note-:0-7">[7]</a> For 3 or more agents, the best known protocol requires O(n3 ε−1) queries.<a href="#cite_note-12">[12]</a></li></ul>

<a href="Maximin_share" title="Maximin share">Maximin share</a> cake-cutting, when the pieces must be separated by a positive distance, cannot be done using finitely-many RW queries. Moreover, even for a single agent, there is no algorithm that computes the agent's maximin-share using finitely-many RW queries. However:<a href="#cite_note-13">[13]</a>

<ul><li>For any ε > 0, it is possible to compute a value between the MMS and the MMS-ε using O(n log ε−1) RW queries.</li>

<li>When the cake is circular (i.e., in <a href="Fair_pie-cutting" title="Fair pie-cutting">fair pie-cutting</a>), it is possible to compute a value between the MMS and the MMS-ε using O(n ε−1) RW queries. It is open whether O(n log ε−1) RW queries suffice.</li></ul>

Average-proportional cake-cutting (i.e., an allocation between n families, such that for each family, the average value is at least 1/n of the total) cannot be computed using finitely-many RW queries, even when there are 2 families with 2 members in each family. The proof is by reduction from equitable cake-cutting.<a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Left-mark_and_right-mark">Left-mark and right-mark</h3></div>

When the value measure of an agent is not strictly positive (i.e., there are parts that the agent values at 0), a mark query can, in principle, return infinitely many values. For example, if an agent values [0,0.9] at 1 and [0.9,1] at 0, then the query Mark(0,1) can return any value between 0.9 and 1. Some algorithms require a more specific value:

<ul><li>The left-mark query, LeftMark(x,r), returns the leftmost (smallest) y such that vi ([x,y]) = r;</li>

<li>The right-mark query, RightMark(x,r), returns the rightmost (largest) y such that vi ([x,y]) = r;</li></ul>

If only one of these two variants is given (in addition to the Eval query), the other variant cannot be computed in finite time.<a href="#cite_note-:1-11">[11]</a>

<div class="mw-heading mw-heading3"><h3 id="Two-dimensional_cakes">Two-dimensional cakes</h3></div>

The RW query model has been generalized to two-dimensional cakes<a href="#cite_note-15">[15]</a> and multi-dimensional cakes.<a href="#cite_note-:12-16">[16]</a>

<div class="mw-heading mw-heading2"><h2 id="Alternative_models">Alternative models</h2></div>

There are many cake-cutting algorithms that do not use the RW model. They usually use one of the following models.

<div class="mw-heading mw-heading3"><h3 id="Direct_revelation_model">Direct revelation model</h3></div>

Algorithms for restricted classes of valuations, such as piecewise-linear, piecewise-constant or piecewise-uniform, which can be given explicitly as input to the algorithm. Some such algorithms were developed for <a href="Truthful_cake-cutting" title="Truthful cake-cutting">truthful cake-cutting</a>.

<div class="mw-heading mw-heading3"><h3 id="Moving-knife_model">Moving-knife model</h3></div>

In this model, there are knives moving continuously along the cake (see <a href="Moving-knife_procedure" title="Moving-knife procedure">moving-knife procedures</a>). This model is related to the RW model as follows: any moving-knife procedure with a fixed number of agents and a fixed number of knives can be simulated using O(log ε−1) RW queries.<a href="#cite_note-:0-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="Simultaneous_queries_model">Simultaneous queries model</h3></div>

In this model, agents simultaneously send discretizations of their preferences. A discretization is a sequence of cut-points, and the values of pieces between these cut-points (for example: a protocol for two agents might require each agent to report a sequence of three cut-points (0,x,1) where the values of (0,x) and (x,1) are 1/2). These reports are used to compute a fair allocation. The complexity of an algorithm in this model is defined as the maximum number of intervals in a required discretization (so the complexity of the above protocol is 2).

One advantage of this model over the RW model is that it enables to elicit preferences in parallel. This allows to compute a <a href="Proportional_cake-cutting" title="Proportional cake-cutting">proportional cake-cutting</a> in time O(n) by simultaneously asking each agent for a discretization with n intervals (of equal value). In contrast, in the RW model there is an O(n log n) lower bound. On the other hand, in the simultaneous model, it is impossible to compute an <a href="Envy-free_cake-cutting" title="Envy-free cake-cutting">envy-free cake-cutting</a> using a finite discretization for 3 or more agents; but for every e>0, there exists a simultaneous protocol with complexity O(n/e2), that attains an e-approximate envy-free division.<a href="#cite_note-17">[17]</a>

<ul><li><a href="Demand_oracle" title="Demand oracle">Demand oracle</a> (and value oracle) - a similar query model in a setting with indivisible objects.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRobertsonWebb1998" class="citation book cs1">Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-56881-076-8</bdi>. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/97041258">97041258</a>. <a href="OL_(identifier)" class="mw-redirect" title="OL (identifier)">OL</a> <a rel="nofollow" class="external text" href="https://openlibrary.org/works/OL2730675W">2730675W</a>.</cite>

</li>

<li id="cite_note-ws07-2">^ <a href="#cite_ref-ws07_2-0">a</a> <a href="#cite_ref-ws07_2-1">b</a> <cite id="CITEREFGerhard_J._Woeginger_and_Jiri_Sgall2007" class="citation journal cs1"><a href="Gerhard_J._Woeginger" title="Gerhard J. Woeginger">Gerhard J. Woeginger and Jiri Sgall</a> (2007). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2006.07.003">"On the complexity of cake cutting"</a>. Discrete Optimization. 4 (2): 213–220. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2006.07.003">10.1016/j.disopt.2006.07.003</a>.</cite>

</li>

<li id="cite_note-ep06neg-3">^ <a href="#cite_ref-ep06neg_3-0">a</a> <a href="#cite_ref-ep06neg_3-1">b</a> <cite id="CITEREFEdmonds2006" class="citation book cs1">Edmonds, Jeff (2006). "Cake cutting really is not a piece of cake". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. pp. 271–278. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.412.7166">10.1.1.412.7166</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1109557.1109588">10.1145/1109557.1109588</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0898716054</bdi>.</cite>, <cite id="CITEREFEdmonds2011" class="citation journal cs1">Edmonds, Jeff (2011). "Cake cutting really is not a piece of cake". ACM Transactions on Algorithms. 7 (4): 1–12. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.1536">10.1.1.146.1536</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2000807.2000819">10.1145/2000807.2000819</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2440968">2440968</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFCsehFleiner2020" class="citation journal cs1">Cseh, Ágnes; Fleiner, Tamás (2020-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3380742">"The Complexity of Cake Cutting with Unequal Shares"</a>. ACM Transactions on Algorithms. 16 (3): 29:1–29:21. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1709.03152">1709.03152</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3380742">10.1145/3380742</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1549-6325">1549-6325</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:218517351">218517351</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFProcaccia2009" class="citation journal cs1">Procaccia, Ariel (2009). <a rel="nofollow" class="external text" href="http://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewFile/274/634">"Thou Shalt Covet Thy Neighbor's Cake"</a>. IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence: 239–244.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFStromquist2008" class="citation journal cs1">Stromquist, Walter (2008). <a rel="nofollow" class="external text" href="http://www.emis.de/journals/EJC/Volume_15/PDF/v15i1r11.pdf">"Envy-free cake divisions cannot be found by finite protocols"</a> (PDF). Electronic Journal of Combinatorics. 15. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F735">10.37236/735</a>.</cite>

</li>

<li id="cite_note-:0-7">^ <a href="#cite_ref-:0_7-0">a</a> <a href="#cite_ref-:0_7-1">b</a> <a href="#cite_ref-:0_7-2">c</a> <a href="#cite_ref-:0_7-3">d</a> <cite id="CITEREFBrânzeiNisan2018" class="citation arxiv cs1">Brânzei, Simina; Nisan, Noam (2018-07-13). "The Query Complexity of Cake Cutting". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1705.02946">1705.02946</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.GT">cs.GT</a>].</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFHollenderRubinstein2023" class="citation book cs1">Hollender, Alexandros; Rubinstein, Aviad (2023). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/10353201">Envy-Free Cake-Cutting for Four Agents</a>. pp. 113–122. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2311.02075">2311.02075</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS57990.2023.00015">10.1109/FOCS57990.2023.00015</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>979-8-3503-1894-4</bdi>. Retrieved 2024-01-04.</cite>

</li>

<li id="cite_note-:2-9">^ <a href="#cite_ref-:2_9-0">a</a> <a href="#cite_ref-:2_9-1">b</a> <cite id="CITEREFProcacciaWang2017" class="citation book cs1">Procaccia, Ariel D.; Wang, Junxing (2017-06-20). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3033274.3085107">"A Lower Bound for Equitable Cake Cutting"</a>. Proceedings of the 2017 ACM Conference on Economics and Computation. EC '17. Cambridge, Massachusetts, USA: Association for Computing Machinery. pp. 479–495. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3033274.3085107">10.1145/3033274.3085107</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-4527-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9834718">9834718</a>.</cite>

</li>

<li id="cite_note-cp11-10"><a href="#cite_ref-cp11_10-0">^</a> <cite id="CITEREFCechlárováPillárová2012" class="citation journal cs1">Cechlárová, Katarína; Pillárová, Eva (2012). "A near equitable 2-person cake cutting algorithm". Optimization. 61 (11): 1321. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F02331934.2011.563306">10.1080/02331934.2011.563306</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:120300612">120300612</a>.</cite>

</li>

<li id="cite_note-:1-11">^ <a href="#cite_ref-:1_11-0">a</a> <a href="#cite_ref-:1_11-1">b</a> <cite id="CITEREFCechlárová,_Katarína;_Pillárová,_Eva2012" class="citation journal cs1">Cechlárová, Katarína; Pillárová, Eva (2012-11-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2012.08.001">"On the computability of equitable divisions"</a>. Discrete Optimization. 9 (4): 249–257. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2012.08.001">10.1016/j.disopt.2012.08.001</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1572-5286">1572-5286</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBrânzeiMiltersen2015" class="citation journal cs1">Brânzei, Simina; Miltersen, Peter Bro (2015-07-25). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/2832249.2832316">"A dictatorship theorem for cake cutting"</a>. Proceedings of the 24th International Conference on Artificial Intelligence. IJCAI'15. Buenos Aires, Argentina: AAAI Press: 482–488. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-57735-738-4</bdi>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFElkindSegal-HaleviSuksompong2022" class="citation journal cs1">Elkind, Edith; Segal-Halevi, Erel; Suksompong, Warut (2022). "Mind the gap: Cake cutting with separation". Artificial Intelligence. 313: 103783. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2012.06682">2012.06682</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.artint.2022.103783">10.1016/j.artint.2022.103783</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:229153490">229153490</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFSegal-HaleviNitzan2019" class="citation journal cs1">Segal-Halevi, Erel; Nitzan, Shmuel (2019-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/s00355-019-01210-9">"Fair cake-cutting among families"</a>. Social Choice and Welfare. 53 (4): 709–740. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1510.03903">1510.03903</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00355-019-01210-9">10.1007/s00355-019-01210-9</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1432-217X">1432-217X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1602396">1602396</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFSegal-HaleviNitzanHassidimAumann2017" class="citation journal cs1">Segal-Halevi, Erel; Nitzan, Shmuel; Hassidim, Avinatan; Aumann, Yonatan (2017). "Fair and square: Cake-cutting in two dimensions". Journal of Mathematical Economics. 70: 1–28. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1409.4511">1409.4511</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jmateco.2017.01.007">10.1016/j.jmateco.2017.01.007</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1278209">1278209</a>.</cite>

</li>

<li id="cite_note-:12-16"><a href="#cite_ref-:12_16-0">^</a> <cite id="CITEREFCsehFleiner2018" class="citation cs2">Cseh, Ágnes; Fleiner, Tamás (2018), "The Complexity of Cake Cutting with Unequal Shares", Algorithmic Game Theory, Springer International Publishing, pp. 19–30, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1709.03152">1709.03152</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-99660-8_3">10.1007/978-3-319-99660-8_3</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783319996592</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19245769">19245769</a></cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFBalkanskiBrânzeiKurokawaProcaccia2014" class="citation journal cs1">Balkanski, Eric; Brânzei, Simina; Kurokawa, David; Procaccia, Ariel (2014-06-21). <a rel="nofollow" class="external text" href="https://ojs.aaai.org/index.php/AAAI/article/view/8802">"Simultaneous Cake Cutting"</a>. Proceedings of the AAAI Conference on Artificial Intelligence. 28 (1). <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1609%2Faaai.v28i1.8802">10.1609/aaai.v28i1.8802</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2374-3468">2374-3468</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1867115">1867115</a>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-06-22" href="https://en.wikipedia.org/wiki/?title=Robertson%E2%80%93Webb_query_model&oldid=1230357887">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>